/**
 * 找主元素
 * 主元素定义为出现次数大于数组长度的一半
 * 查找方法可以这样理解，主元素个数大于数组长度的一半，
 * 那么如果想办法将主元素和其他元素抵消，那么最后剩下的一定就是主元素
 * 
 * 时间复杂度为O(n),空间复杂度为O(1)
 * 
 * 注意：可以使用先排序，再计数的方法，此时复杂度为n*Log(2n)
 * 复杂度高一点，但是算法思想和过程全对，不会扣太多的分
 * 甚至写出O(n^2)的算法，全写对也是可以拿到10分的
 */

int majority(int a[],int n){
    int i,c,count=1;
    c=a[0];//将第一个元素标记为主元素
    for(i=1;i<n;i++){
        if(a[i]==c){//标记的元素如果和当前元素相等，计数+1
            count++;
        }else{
            if(count>0) count--;
            else{c=a[i]; count=1;}//如果不相等，就抵消一个，然后重新计数
        }
    }
    if(count>0){//统计实际出现的次数
        count=0;
        for(i=0;i<n;i++){
            if(a[i]==c){
                count++;
            }
        } 
    }
    if(count>n/2) return c;//确定候选元素
    else return -1;//不存在主元素

}